/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/unique-paths-iii
   @Language: C++
   @Datetime: 19-04-08 16:23
   */

class Solution {
public:
	/*
	 * @param : an array of arrays
	 * @return: the sum of all unique weighted paths
	 */
	int uniqueWeightedPaths(vector<vector<int>>& grid) {
		// write your codes here
		if(grid.size()<1 || grid[0].size()<1) return 0;
		int m=grid.size(), n=grid[0].size();
		vector<vector<unordered_set<int> > > dp(m,vector<unordered_set<int> >(n));
		dp[0][0].insert(grid[0][0]);
		for(int i=0; i<m; ++i){
			for(int j=0; j<n; ++j){
				if(i>0)
					for(const auto &s:dp[i-1][j])
						dp[i][j].insert(s+grid[i][j]);
				if(j>0)
					for(const auto &s:dp[i][j-1])
						dp[i][j].insert(s+grid[i][j]);
			}
		}
		int sum=0;
		for(const auto &s:dp[m-1][n-1])
			sum+=s;
		return sum;
	}
};
